package com.yangli.leecode.mashib.interview;

/**
 * @Description
 * @Author liyang
 * @Date 2023/3/3 15:40
 */
public class TwentySeven {
    public static void main(String[] args){
        System.out.println(TwentySeven.shortestBridge(new int[][]{{0, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1}}));
    }


    //1,一维数组常数项优化，比二维数组效率高
    public static int shortestBridge(int[][] m){
        int N = m.length;
        int M = m[0].length;
        int all = N * M;
        int island = 0;
        int[] curs = new int[all];//表示所有1的  一维位置信息  ==>一维数组常数项的优化，用二维数组效率低
        int[] nexts = new int[all];//下一圈的位置
        int[][] record = new int[2][all];//两片岛，每片岛位置的记录
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (m[i][j] == 1) {
                    //找出这个1关联的这片岛 并且改成2  并且记录岛curs里面，并记录距离record
                    int queueSize = infect(m, i, j, N, M, curs, 0, record[island]);

                    int V = 1;//广播层级
                    while (queueSize != 0) {
                        V++;
                        queueSize = bfs(N, M, all, V, curs, queueSize, nexts, record[island]);//利用curs的记录，广度搜索为0的记录，主要是为了统计record[island]的距离
                        int[] temp = curs;
                        curs = nexts;
                        nexts = temp;
                    }
                    island++;
                }
            }

        }
        int min = Integer.MIN_VALUE;
        for (int i = 0; i < all; i++) {
            min = Math.min(min, record[0][i] + record[1][i]);
        }
        return min - 3;

    }


    //从m[i][j]感染出去(找到这一片岛所有的1)，把这片岛的位置放到curs[]一维队列中。
    //1(a,b) ->curs[index++] = (a*m+b)
    //record[a*m+b]=1 记录某个岛之间的距离
    public static int infect(int[][] m, int i, int j, int N, int M, int[] curs, int index, int[] record){
        if (i < 0 || j < 0 || i == N || j == M || m[i][j] != 1) {
            return index;
        }
        m[i][j] = 2;//防止重复调用
        int p = i * M + j;
        curs[index++] = p;
        record[p] = 1;
        index = infect(m, i - 1, j, N, M, curs, index, record);
        index = infect(m, i + 1, j, N, M, curs, index, record);
        index = infect(m, i, j - 1, N, M, curs, index, record);
        index = infect(m, i, j + 1, N, M, curs, index, record);
        return index;
    }


    //curs里面点上下左右,走record==0的点，
    public static int bfs(int N, int M, int all, int V, int[] curs, int queueSize, int[] nexts, int[] record){
        int nexti = 0;
        for (int i = 0; i < queueSize; i++) {//用一维数组表示二维数组，点上下左右一定的位置变化规律
            int up = curs[i] / N != 0 ? curs[i] - N : -1;
            int down = curs[i] / N != N - 1 ? curs[i] + N : -1;
            int left = curs[i] % M != 0 ? curs[i] - M : -1;
            int right = curs[i] % M != M - 1 ? curs[i] + M : -1;
            if (up != -1 && record[up] == 0) {
                nexts[nexti++] = up;
                record[up] = V;
            }
            if (down != -1 && record[down] == 0) {
                nexts[nexti++] = down;
                record[down] = V;
            }
            if (left != -1 && record[left] == 0) {
                nexts[nexti++] = left;
                record[left] = V;
            }
            if (right != -1 && record[right] == 0) {
                nexts[nexti++] = right;
                record[right] = V;
            }
        }
        return nexti;

    }

}
